---

dePolyABT.hpp

Go to the documentation of this file.

///////////////////////////////////////////////////////////////////////////////
/// @file dePolyABT.hpp
///
/// @brief Adaptive Binary Tree for polygons
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Mar 2003
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DE_POLYABT_HPP
#define DE_POLYABT_HPP

#include "deGlobalTypes.hpp"
#include "deArray.hpp"
#include "deSurface.hpp"
#include "deScene.hpp"
#include "deMath.hpp"
#include "deWorld_Helper.hpp"

class IdeVertexBuffer;
class IdeSceneObject;

const int deABT_TexCoords = 4;

class dePolyABT
{
public:
    // all vertices stored in the ABT structure will store this information only
    struct ABTVertex
    {
        deVec3d     Position;
        deVec3f     Normal;
        deTexCoord2 TexCoords[deABT_TexCoords];
        deARGB      Diffuse;
    };
    // all ABT faces are triangles, and each knows its surface ID
    struct ABTFace
    {
        long Indices[3];
        long SurfaceID;
    };
    enum ABTSplitMethod
    {
        Split_NoMethod,
        Split_SuccessiveApprox,
        Split_AllVerts,
        Split_MultiSample,
        Split_Statistical,
        Split_Count,
        Split_Force32Bit = 0x7fffffff
    };

    dePolyABT();
    ~dePolyABT();

    /// surface state machine setting
    deBoolean SetCurrentSurface(IdeSurface* CurrSurface);

    /// add vertices that will be indexed by faces
    deBoolean AddVertices(ABTVertex* VertexArray, long NumVerts, long & BaseVertexIndex, const deTransformInfo & worldpos);
    /// add indices for faces, offset by a value obtained from AddVertices
    deBoolean AddTriangleIndices(long* IndexArray, long BaseVertexIndex, long NumIndices);
    /// handles an entire sceneobject without decomposing it into geometry
    deBoolean AddSceneObject(IdeSceneObject* pObject);
    /// add raw geometry from a vertex buffer - can be just vertices, just indices, or both
    deBoolean AddIndexedVBuffer(IdeVertexBuffer* VBuffer, long & BaseVertexIndex, const deTransformInfo & worldpos);
    /// add the geometry from an IdeMesh object
    deBoolean AddMeshGeometry(IdeMesh* pMesh, const deTransformInfo & worldpos);

    /// set the threshold for maximum triangles in a leaf node. defaults to 50.
    deBoolean SetMaxLeafTris(long MaxTris);
    /// set the threshold for maximum triangles in a renderable vertex buffer. defaults to 2000.
    deBoolean SetMaxVBufferTris(long MaxTris);
    /// set the weighting values for determining split plane locations.
    /// sum of all weights should be 1.0, and will be normalized if it is not.
    /// recommended to put most weight into FaceBalance to get more adaptive splits,
    /// but leave some weight in the others to avoid degenerate splits.
    /// @param Axis weight towards largest axis
    /// @param Volume weight towards center of chunk volume
    /// @param FaceBalance weight towards equal number of faces on each side of split
    /// @param NumSplit weight away from inducing splits of faces in a node
    deBoolean SetSplitWeights(deFloat Axis, deFloat Volume, deFloat FaceBalance, deFloat NumSplit);

    /// compile the entire ABT geometry into renderable VBs and leaf nodes
    deBoolean CompileABT();

    /// render the currently visible geometry, according to the input Params.
    deBoolean RenderVisibleGeometry(IdeSceneGraph::deSceneTraversal* Params);

    /// get the AABB extents of the ABT
    void GetVisibleAABB(deAABB& bbox);

    // serialization stuff
    deBoolean Serialize(IdeFile * File);
    deBoolean DeSerialize(IdeFile * File, u32 DataLength, u32 & AmtRead);
    deBoolean DeSerializeLoad();

private:
    /// a split in an ABT node, along an axis (0,1,2) at a certain percentage
    struct ABTSplit
    {
        long        Axis;
        deDouble    Percent;
    };
    /// a chunk of geometry that can be rendered independently.
    /// chunks should generally be 2000 faces or more
    struct ABTRenderChunk
    {
        IdeVertexBuffer*    VBuffer;
        u32                 Surface;
    };
    /// a partition within the ABT.
    /// either has children or renderables, never both.
    /// non-leaf nodes can have faces if in limbo while compiling.
    struct ABTPartition
    {
        deAABB BBox;
        ABTSplit Split;
        deTArray <long> SceneObjectList;
        deTArray<ABTFace>   Faces;
        deTArray<ABTRenderChunk> Renderables;
        ABTPartition* Children[2]; // 0 = minside, 1 = maxside
        ABTPartition* Parent;
        deBoolean RenderableBuilt;
    };
    /// information about a split - most important being the score.
    /// used only while partitioning a box, to score the various sampled splits
    struct ABTSplitStat
    {
        ABTSplit Split;
        dePlane Plane;
        long FrontBackDiff;
        long NumOn;
        deFloat Score;
    };

    deTArray<ABTVertex>     m_Vertices;
    deTArray<ABTFace>       m_AllFaces;
    deTArray<IdeSurface*>   m_Surfaces;
    deTArray<IdeSceneObject*>   m_SceneObjects;
    deAABB                  m_TotalBBox;
    deVec3d                 m_WorldOffset;
    ABTPartition*           m_RootPartition;
    u32                     m_CurrSurfaceIndex;
    u32                     m_OriginalVertNum;
    u32                     m_MaxLeafTris;
    u32                     m_MaxVBTris;
    deFloat                 m_SplitWeights[4];

    // setup
    void            DestroyABT();
    // building the ABT
    ABTPartition*   CreateABTPartition(ABTPartition * Parent, int ChildNum);
    deBoolean       DestroyABTPartition(ABTPartition* &pPart);
    deBoolean       ShrinkPartitionBBoxes(ABTPartition * Parent);
    deBoolean       ProcessABTPartition(ABTPartition * pPart);
    void            PickBestSplit(const ABTPartition* pPart, ABTSplitStat & best, ABTSplitMethod method) const;
    deBoolean       ScorePartitionSplit(const ABTPartition* pPart, ABTSplitStat * pStat, deFloat AxisScores[3]) const;
    deBoolean       InterpolateCutEdge(ABTVertex * NewVert, long Index1, long Index2, dePlane& SplitPlane);
    deBoolean       BuildPartitionVBuffer(ABTPartition* pPart);

    // using the ABT
    deBoolean       RenderVisibleABTPartitions(IdeSceneGraph::deSceneTraversal* Params, ABTPartition* CurrentPart, deBoolean AllVisible);
    deBoolean       RenderABTPartition(IdeSceneGraph::deSceneTraversal* Params, ABTPartition* pPart);

    // stuff for serialization
    deTArray<deIDPair> m_SerialSurfaces, m_SerialObjects;
    struct ABTFilePartition_01
    {
        deAABB BBox;
        ABTSplit Split;
        u32 childPart[2]; u32 parentPart;
        u32 numFaces, faceIndexStart;
        u32 numObjects, objectIndexStart;
    };
    static u32 AppendFilePartition(deTArray<ABTFilePartition_01> & fileparts, const ABTPartition* current, u32 parentIdx, u32 & TotalFaces, u32 & TotalObjects);
    ABTPartition* DecomposeFilePartition(const deTArray<ABTFilePartition_01> & fileparts, u32 currentIdx, ABTPartition* parent, const deTArray<u32> objectIndices, const deTArray<ABTFace> faces);
    struct readWriteObject_t
    {
        IdeFile * m_File;
        deBoolean m_Write;
        u32 m_DataLength, *m_AmtRead;
        deBoolean operator()(IdeWorldObject* obj);
    };
    struct readWriteVertex_t
    {
        IdeFile * m_File;
        deBoolean m_Write;
        u32 m_DataLength, *m_AmtRead;
        deBoolean operator()(ABTVertex& vert);
    };
    struct readWriteFace_t
    {
        IdeFile * m_File;
        deBoolean m_Write;
        u32 m_DataLength, *m_AmtRead;
        deBoolean operator()(ABTFace& face);
    };
    struct readWritePartition_t
    {
        IdeFile * m_File;
        deBoolean m_Write;
        u32 m_DataLength, *m_AmtRead;
        deBoolean operator()(ABTFilePartition_01& part);
    };
    struct grabPartitionData_t
    {
        deTArray<u32> objects;
        deTArray<ABTFace> faces;
        deBoolean operator()(ABTFilePartition_01& part);
    };
};

#endif // DE_POLYABT_HPP

---